package com.sicheng.lc.杂题.二叉树;

import leetcode.editor.cn.tree.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/9/6 23:08
 */
public class 锯齿形访问二叉树 {
    //https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayList<List<Integer>> res = new ArrayList<>();
        if (root == null)
            return res;
        ArrayDeque<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        boolean left = false;
        while (!q.isEmpty()) {
            ArrayDeque<Integer> layer = new ArrayDeque<>();
            int size = q.size();
            left = !left;
            for (int i = 0; i < size; i++) {
                TreeNode x = q.poll();
                assert x != null;
                if (left)
                    layer.offer(x.val);
                else
                    layer.push(x.val);
                if (x.left != null)
                    q.offer(x.left);
                if (x.right != null)
                    q.offer(x.right);
            }
            res.add(new ArrayList<>(layer));

        }

        return res;
    }

}
